#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>
#include "LRU.h"
#define OK 1
#define TRUE 1
#define FALSE 0
// typedef int ElemeType;
// typedef int Status;
//定义读写比例值的
int Cw_temp=9;
int Cr_temp=1;

//typedef struct BufNode
//{
//    ElemeType LPN;//输入的LPN号
//    int isD;//脏页标识符
//    struct BufNode *pre,*next;
//}BufNode,*BufList;


//函数定义声明
//首先创建两个队列一个DLRU，一个CLRU
void InitCLRUList(BufList *CHead);
void InitDLRUList(BufList *DHead);
//释放和销毁两个链表队列
Status DestroyCLRUList(BufList *CHead);
Status DestroyDLRUList(BufList *Dhead);
//遍历两链表查看是否存在LPN,存在返回指向该节点的值BufNode类型的指针
BufList FindLPNinCLRU(BufList CHead,ElemeType LPN);
BufList FindLPNinDLRU(BufList Dhead,ElemeType LPN);
//计算两个链表的长度
Status CLRULength(BufList CHead);
Status DLRULength(BufList DHead);
//将新的请求加入到各自的链表中去
Status AddNewToCLRU(BufList CHead,ElemeType LPN,int flag);
Status AddNewToDLRU(BufList DHead,ElemeType LPN,int flag);
//删除各自的LRU位置的项
Status DeleteCLRUend(BufList CHead);
Status DeleteDLRUend(BufList DHead);
//将命中的LPN移动到MRU位置
Status MoveCLRUtoDLRU(BufList DHead,BufList HitLPN);
//更新目标队列tau的值
int ComputeTau(BufList DHead,BufList CHead,int *tau,int flag);

//函数实体定义
void InitCLRUList(BufList *CHead)
{
    *CHead=(BufList)malloc(sizeof(BufNode));
    if(*CHead==NULL)
    {
        printf("CLRU链表初始化失败\n");
        getchar();
        exit(0);
    }else
    {
        //L就是虚拟表头
        (*CHead)->next=(*CHead)->pre=*CHead;
    }
}

void InitDLRUList(BufList *DHead)
{
    *DHead=(BufList)malloc(sizeof(BufNode));
    if(*DHead==NULL)
    {
        printf("DLRU双链表初始化失败\n");
        getchar();
        exit(0);
    }else
    {
        //DHEAD就是虚拟表头
        (*DHead)->next=(*DHead)->pre=*DHead;
    }
}

Status DestroyCLRUList(BufList *CHead)
{
/* 操作结果：销毁双向循环链表L */
   BufList q,p=(*CHead)->next; /* p指向第一个结点 */
   while(p!=*CHead) /* p没到表头 */
   {
     q=p->next;
     free(p);
     p=q;
   }
   free(*CHead);
   *CHead=NULL;
   return OK;
}

Status DestroyDLRUList(BufList *DHead)
{
/* 操作结果：销毁双向循环链表L */
    BufList q,p=(*DHead)->next; /* p指向第一个结点 */
   while(p!=*DHead) /* p没到表头 */
   {
     q=p->next;
     free(p);
     p=q;
   }
   free(*DHead);
   *DHead=NULL;
   return OK;
}

BufList FindLPNinCLRU(BufList CHead,ElemeType LPN)
{
     /*从CLRU双链表中寻找是否存在该LPN号的页，存在则返回该页的位置指针
     若不存在，返回的地址是NULL*/
     BufList r,p;
     r=NULL;
     p=CHead->next;
     while(p!=CHead)
     {
         if(p->LPN==LPN)
         {
             /*表示存在该LPN号*/
             r=p;//将该数据页的地址返回
             return r;
         }
         p=p->next;
     }
     return r;//此时返回的r是NULL
}

BufList FindLPNinDLRU(BufList DHead,ElemeType LPN)
{
     /*从DLRU双链表中寻找是否存在该LPN号的页，存在则返回该页的位置指针
     若不存在，返回的地址是NULL*/
     BufList r,p;
     r=NULL;
     p=DHead->next;
     while(p!=DHead)
     {
         if(p->LPN==LPN)
         {
             /*表示存在该LPN号*/
             r=p;//将该数据页的地址返回
             return r;
         }
         p=p->next;
     }
     return r;//此时返回的r是NULL
}

Status CLRULength(BufList CHead)
{
/* 初始条件：CHead已存在。操作结果：返回CHead中数据元素个数 */
   int i=0;
   BufList p=CHead->next; /* p指向第一个结点 */
   while(p!=CHead) /* p没到表头 */
   {
     i++;
     p=p->next;
   }
   return i;
}

Status DLRULength(BufList DHead)
{
/* 初始条件：DHead已存在。操作结果：返回DHead中数据元素个数 */
   int i=0;
   BufList p=DHead->next; /* p指向第一个结点 */
   while(p!=DHead) /* p没到表头 */
   {
     i++;
     p=p->next;
   }
   return i;
}

Status AddNewToCLRU(BufList CHead,ElemeType LPN,int flag)
{
    //参数说明1LPN,2操作类型，一般写操作为0
    BufList temp=NULL;
    temp=(BufList)malloc(sizeof(BufNode));
    if(temp==NULL)
    {
        fprintf(stderr,"AddNewToCLRU节点分配内存错误\n");
        getchar();
        exit(0);
    }
    temp->isD=flag;
    temp->LPN=LPN;
    //将节点嵌入到MRU位置
    CHead->next->pre=temp;
    temp->next=CHead->next;
    temp->pre=CHead;
    CHead->next=temp;
    return OK;
}

Status AddNewToDLRU(BufList DHead,ElemeType LPN,int flag)
{
    //参数说明1LPN,2操作类型，一般写操作为0
    BufList temp=NULL;
    temp=(BufList)malloc(sizeof(BufNode));
    if(temp==NULL)
    {
        fprintf(stderr,"节点分配内存错误\n");
        getchar();
        exit(0);
    }
    temp->isD=flag;
    temp->LPN=LPN;
    //将节点嵌入到MRU位置
    DHead->next->pre=temp;
    temp->next=DHead->next;
    temp->pre=DHead;
    DHead->next=temp;
    return OK;
}


Status DeleteCLRUend(BufList CHead)
{
    //剔除操作是脏页的时候，返回的是0.非脏页为非零值
    //实际CLRU剔除的都是干净页
    BufList p,q;
    p=CHead->pre;
    q=p->pre;
    int flag=p->isD;
    q->next=CHead;
    CHead->pre=q;
    //释放LRU位置的数据
    free(p);
    return flag;
}

Status DeleteDLRUend(BufList DHead)
{
    //剔除操作是脏页的时候，返回的是0.非脏页为非零值
    BufList p,q;
    p=DHead->pre;
    q=p->pre;
    int flag=p->isD;
    q->next=DHead;
    DHead->pre=q;
    //释放LRU位置的数据
    free(p);
    return flag;
}
//该函数实现将CLRU中命中的节点转移置DLRU节点的MRU位置,
Status MoveCLRUtoDLRU(BufList DHead,BufList HitLPN)
{
    BufList temp;
    temp=HitLPN->pre;
    //先从CLRU的链表中删除该命中节点
    temp->next=HitLPN->next;
    HitLPN->next->pre=temp;
    //将该节点插入到DLRU的MRU位置
    DHead->next->pre=HitLPN;
    HitLPN->next=DHead->next;
    DHead->next=HitLPN;
    HitLPN->pre=DHead;
    return OK;
}

int ComputeTau(BufList DHead,BufList CHead,int *tau,int flag)
{
    int DL=DLRULength(DHead);
    int CL=CLRULength(CHead);
    //根据读写代价归一化占比
    double Cr=(double)Cr_temp/(Cr_temp+Cw_temp);
    double Cw=(double)Cw_temp/(Cr_temp+Cw_temp);
    //t是*tau的增加值或者减小值,tp是为了实现计算四舍五入的中间值
    double tp=0.0;
    int t=0;
    //根据命中的区域来区别操作
    //flag=0,命中DLRU（减小tau）
    //flag!=0,命中CLRU（增加tau）
    if(flag)
    {
        //命中CLRU，增加tau
        tp=((double)DL/CL)*Cr;
        //对增加值进行四舍五入计算
        t=(int)(tp+0.5)>(int)tp?(int)tp+1:(int)tp;
        *tau=*tau+t;
    }else
    {
        //命中DLRU,减小tau
        tp=((double)CL/DL)*Cw;
        //对增加值进行四舍五入计算
        t=(int)(tp+0.5)>(int)tp?(int)tp+1:(int)tp;
        *tau=*tau-t;
        //防止出现tau值为负
        if(*tau<0)
        {
            *tau=0;
        }
    }
    //返回值为更改后的tau值
    return OK;
}
